package leetcode.L51;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        //使用集合的回溯法
        List<List<String>> res = new ArrayList<>();
        //定义columns
        int[] queens = new int[n];
        Arrays.fill(queens,-1);

        HashSet<Integer> columns = new HashSet<>();
        //定义左上到右下 行下标和列下标相减值相等
        HashSet<Integer> d1 = new HashSet<>();
        //定义右上到左下 行下标和列下标相加值相等
        HashSet<Integer> d2 = new HashSet<>();
        //from the 0 row
        backTrack(res,queens,columns,d1,d2,n,0);
        return res;
    }

    //定义从某行开始放一个皇后，由于是每行，因此一定不会重复
    public void backTrack(List<List<String>> res,int[] queens,HashSet columns,HashSet d1,HashSet d2,int n,int row) {
        //遍历到m行作为终止条件
        if (row == n) {
            //遍历columns来获取最终答案
            List<String> board = generateBoard(queens, n);
            res.add(board);
        }else{
            //从第0列开始尝试
            for (int i = 0; i < n; i++) {
                if (columns.contains(i)) {
                    continue;
                }
                int d1Val = row - i;
                if (d1.contains(d1Val)) {
                    continue;
                }
                int d2Val = row + i;
                if (d2.contains(d2Val)) {
                    continue;
                }
                queens[row]=i;
                columns.add(i);
                d1.add(d1Val);
                d2.add(d2Val);
                backTrack(res,queens,columns, d1, d2, n, row + 1);
                queens[row]=-1;
                columns.remove(i);
                d1.remove(d1Val);
                d2.remove(d2Val);
            }
        }
    }
    public List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}
